package leetcode.editor.cn.q1_300.q50;

import leetcode.editor.cn.util.tree.btree.TreeNode;

/**
 * 好吧，这题让我复习了一次 morris 遍历
 *
 * @author qidi
 * @date 2021-12-31 15:31:27
 */
class Q0099_RecoverBinarySearchTree {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public void recoverTree(TreeNode root) {
            TreeNode cur = root;

            TreeNode pre = null;
            TreeNode targetNode1 = null;
            TreeNode targetNode2 = null;

            while (cur != null) {
                if (cur.left != null) {
                    TreeNode mostRight = cur.left;
                    while (mostRight.right != null && mostRight.right != cur) {
                        mostRight = mostRight.right;
                    }

                    if (mostRight.right == null) {
                        mostRight.right = cur;
                        cur = cur.left;
                    } else {
                        if (pre != null && cur.val < pre.val) {
                            targetNode2 = cur;
                            if (targetNode1 == null) {
                                targetNode1 = pre;
                            }
                        }
                        pre = cur;

                        mostRight.right = null;
                        cur = cur.right;
                    }
                } else {
                    if (pre != null && cur.val < pre.val) {
                        targetNode2 = cur;
                        if (targetNode1 == null) {
                            targetNode1 = pre;
                        }
                    }
                    pre = cur;
                    cur = cur.right;
                }
            }

            int v = targetNode1.val;
            targetNode1.val = targetNode2.val;
            targetNode2.val = v;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0099_RecoverBinarySearchTree().new Solution();
    }
}